/**
 * @file 014.字符串中的变位词.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-08
 *
 * @copyright Copyright (c) 2021
 *
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    bool checkInclusion(string s1, string s2)
    {
        // 先把s1打表，然后滑窗判断，窗口大小就是s1.size()
        int m = s1.size(), n = s2.size();
        if (m > n) {
            return false;
        }
        vector<int> cnt(26, 0);
        for (int i = 0; i < m; ++i) {
            ++cnt[s1[i] - 'a'];
            --cnt[s2[i] - 'a'];
        }
        if (isZero(cnt)) {
            return true;
        }
        for (int i = m; i < n; ++i) {
            --cnt[s2[i] - 'a'];
            ++cnt[s2[i - m] - 'a'];
            if (isZero(cnt)) {
                return true;
            }
        }
        return false;
    }

private:
    bool isZero(vector<int> &nums)
    {
        for (auto &num : nums) { // O(26)
            if (num != 0) {
                return false;
            }
        }
        return true;
    }
};

int main()
{
    cout << Solution().checkInclusion("ab", "eidbaooo") << endl;
    cout << Solution().checkInclusion("ab", "eidboaoo") << endl;
    return 0;
}